/*
 * @lc app=leetcode.cn id=52 lang=cpp
 *
 * [52] N皇后 II
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<vector<string>> ans;
    int n;
    bool check(vector<string> &v)
    {
        int dr[4] = {1, 1, -1, -1};
        int dl[4] = {1, -1, 1, -1};
        for (int r = 0; r < n; r++)
        {
            for (int l = 0; l < n; l++)
            {
                if (v[r][l] == 'Q')
                {
                    int last_r = r, last_l = l;
                    for (int i = 0; i < 4; i++)
                    {
                        do
                        {
                            r += dr[i];
                            l += dl[i];
                            if (r >= 0 && r < n && l >= 0 && l < n && v[r][l] == 'Q')
                            {
                                return false;
                            }
                        } while (r >= 0 && r < n && l >= 0 && l < n);
                        r = last_r, l = last_l;
                    }
                    r = last_r, l = last_l;
                }
            }
        }

        return true;
    }

    /**
     * @brief 
     * 
     * @param v 
     * @param flag 用于指示该列是否防止了Q
     * @param inx 到目前位置已经放置了多少个Q
     * @param start_r 从哪一行开始搜索，防止出现重复
     * @return true 
     * @return false 
     */
    void dfs(vector<string>& v, string& flag, int inx, int start_r)
    {
        if(inx == n)
        {
            if(check(v))
            {
                ans.push_back(v);
                return;
            }
            return;
        }
        
        for(int r = start_r; r < n; r++)
        {
            if(v[r].find('Q') == v[r].npos)//不能有同行的
                for(int l = 0; l < n; l++)
                {
                    if(flag[l] != 'Q' && v[r][l] != 'Q')
                    {
                        v[r][l] = 'Q';
                        flag[l] = 'Q';
                        dfs(v, flag, inx+1, r + 1);
                        v[r][l] = '.';
                        flag[l] = '.';
                    }
                }
        }
        return;
    }

    vector<vector<string>> solveNQueens(int n)
    {
        vector<string> v;
        this->n = n;
        char tmp[1024] = {0};
        memset(tmp, '.', n);
        for(int i = 0; i < n; i++)
        {
            v.push_back(string(tmp));
        }
        string s(tmp);
        dfs(v, s, 0, 0);
        return ans;
    }
    int totalNQueens(int n) {
        return solveNQueens(n).size();
    }
};



// int main()
// {
//     Solution s;
//     s.solveNQueens(4);
//     return 0;
// }
// @lc code=end


// @lc code=end

